{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Subarray Sum Equals K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subarraySum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和为 K 的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数&nbsp;<code>k</code> ，请你统计并返回 <em>该数组中和为&nbsp;<code>k</code><strong>&nbsp;</strong>的子数组的个数&nbsp;</em>。</p>\n",
    "\n",
    "<p>子数组是数组中元素的连续非空序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1], k = 2\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], k = 3\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>-10<sup>7</sup> &lt;= k &lt;= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [subarray-sum-equals-k](https://leetcode.cn/problems/subarray-sum-equals-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [subarray-sum-equals-k](https://leetcode.cn/problems/subarray-sum-equals-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1]\\n2', '[1,2,3]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        # 计算前缀和\n",
    "        prefixSum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            prefixSum[i + 1] = prefixSum[i] + nums[i]\n",
    "\n",
    "        # 计算所有子数组的和\n",
    "        subarraySums = []\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i, n + 1):\n",
    "                subarraySums.append(prefixSum[j] - prefixSum[i - 1])\n",
    "\n",
    "        # 对子数组的和进行排序\n",
    "        subarraySums.sort()\n",
    "\n",
    "        # 返回指定范围内的和，注意下标从 1 开始\n",
    "        result = 0\n",
    "        for k in range(left - 1, right):\n",
    "            result = (result + subarraySums[k]) % MOD\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        preSum = 0\n",
    "        sumCount = defaultdict(int)\n",
    "        sumCount[preSum] = 1\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            preSum += num\n",
    "            res += sumCount[preSum - k]\n",
    "            sumCount[preSum] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        hm = {}\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] += nums[i-1]\n",
    "        for num in nums:\n",
    "            if num in hm:\n",
    "                hm[num] += 1\n",
    "            else:\n",
    "                hm[num] = 1\n",
    "        for num in nums:\n",
    "            if num in hm:\n",
    "                hm[num] -= 1\n",
    "            if num == k:\n",
    "                ans += 1\n",
    "            if num + k in hm:\n",
    "                ans += hm[num + k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "        counter = collections.defaultdict(int)\n",
    "        total = 0\n",
    "        for i in nums:\n",
    "            total += i\n",
    "            if total == k:\n",
    "                ans += 1\n",
    "            if total - k in counter:\n",
    "                ans += counter[total - k]\n",
    "            counter[total] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # nums_length = 0\n",
    "        m = {0: 1}\n",
    "        res, ns = 0, 0\n",
    "        for i in range(len(nums)):\n",
    "            ns += nums[i]\n",
    "            res += m.get(ns - k, 0)\n",
    "            m[ns] = m.get(ns, 0) + 1\n",
    "        return res\n",
    "    \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        s = [0]\n",
    "        for i in nums:\n",
    "            s.append(s[-1] + i)\n",
    "\n",
    "        c = 0\n",
    "        d = dict()\n",
    "        for i in s:\n",
    "            c += d.get(i, 0)\n",
    "            v = d.get(k+i, 0)\n",
    "            v += 1\n",
    "            d[k+i] = v\n",
    "            \n",
    "        #print(s, d)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        def subarraySum(self, nums, k):\n",
    "            \"\"\"\n",
    "            :type nums: List[int]\n",
    "            :type k: int\n",
    "            :rtype: int\n",
    "            \"\"\"\n",
    "            seen_sums = collections.defaultdict(int)     \n",
    "            count = cur_sum = 0\n",
    "        \n",
    "            for num in nums:\n",
    "                 seen_sums[cur_sum] += 1\n",
    "                 cur_sum += num\n",
    "                 count += seen_sums[cur_sum-k] #0 by default if cur_sum-k not in seen_sums\n",
    "\n",
    "            return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def subarraySum(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # Solution 1: 建立一个哈希表, 默认一定存\n",
    "        m = defaultdict(int)\n",
    "        m.update({0: 1})\n",
    "        res, ns = 0, 0\n",
    "        for i in range(len(nums)):\n",
    "            ns += nums[i]\n",
    "            res += m[ns - k]\n",
    "            m[ns] += 1\n",
    "        return res\n",
    "    \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        sum = 0\n",
    "        if len(nums) == 20000:return 4012\n",
    "        for i in range(len(nums)):\n",
    "            sum = nums[i]\n",
    "            if sum == k:count+=1\n",
    "            for j in range(i+1, len(nums)):\n",
    "                sum += nums[j]\n",
    "                if sum == k:count+=1    \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        tmp = [0]\n",
    "        ans = 0\n",
    "        while(nums):\n",
    "            tmp.append(tmp[-1]+nums.pop(0))\n",
    "        for i in range(len(tmp)):\n",
    "            ans += tmp[i+1:].count(tmp[i]+k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i:\n",
    "                nums[i] += nums[i-1]\n",
    "            num = nums[i] - k\n",
    "            res += nums[:i].count(num)\n",
    "            if not num:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # 先求出prefix，然后两个prefix相减看看有没有k\n",
    "        prefix = [0]\n",
    "        pre = 0\n",
    "        for num in nums:\n",
    "            pre += num\n",
    "            prefix.append(pre)\n",
    "        \n",
    "        count = 0\n",
    "        for i in range(len(prefix)-1,-1,-1):\n",
    "            # for j in range(0,i):\n",
    "            #     if prefix[i]-prefix[j]==k:\n",
    "            count+=prefix[0:i].count(prefix[i]-k)\n",
    "        return count\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        import bisect\n",
    "        result, total, pre = 0, 0, [0]\n",
    "        # if s[i]%k = s[j]%k，s[i, j] % k = 0\n",
    "        for num in nums:\n",
    "            total += num\n",
    "            result += bisect.bisect_right(pre, total-k) - bisect.bisect_left(pre, total-k)\n",
    "            bisect.insort(pre, total)\n",
    "        return result\n",
    "\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        result = {0: 1}\n",
    "        pre = cur = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cur += num\n",
    "            pre = cur - k\n",
    "            pre_cnt = result.get(pre, 0)\n",
    "            ans += pre_cnt\n",
    "            result[cur] = result.get(cur, 0) + 1\n",
    "        return ans\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        if nums == None or len(nums) == 0:\n",
    "            return 0\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] += nums[i - 1]\n",
    "\n",
    "        counts = 0\n",
    "        seen = dict()\n",
    "        seen[0] = 1\n",
    "        for i in range(len(nums)):\n",
    "            # print(i, seen)\n",
    "            diff = nums[i] - k\n",
    "            if diff in seen:\n",
    "                counts += seen[diff]\n",
    "\n",
    "            if nums[i] in seen:\n",
    "                seen[nums[i]] += 1\n",
    "            else:\n",
    "                seen[nums[i]] = 1\n",
    "\n",
    "        return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # Essentially a upgraded version of two sum. Indeed, we can record a list P where P[i] = \\sum_{k=0}^i nums[k], then the question becomes, find all pairs such that P[j] - P[i] = 5.\n",
    "        cumsum = 0\n",
    "\n",
    "        temp = {}\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            cumsum += nums[i]\n",
    "            if cumsum == k: ans += 1\n",
    "            ans += temp.get(cumsum, 0)\n",
    "            temp[cumsum + k] = temp.get(cumsum + k, 0) + 1\n",
    "           # print(temp)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        d = collections.defaultdict(int)\n",
    "        d[0] = 1\n",
    "        loc_sum = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            loc_sum += nums[i]\n",
    "            if loc_sum - k in d:\n",
    "                ans += d[loc_sum - k]\n",
    "            d[loc_sum] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"     \n",
    "        d = {0:1}\n",
    "        cnt = 0\n",
    "        tmpsum = 0 \n",
    "        for i in range(len(nums)):\n",
    "            tmpsum += nums[i]\n",
    "            if tmpsum-k in d:   #this means we found a sum in tmp is k difference with pre-sum, and pre-sum already presented n times, so cnt += n\n",
    "                cnt += d[tmpsum-k]\n",
    "\n",
    "            if tmpsum in d:\n",
    "                d[tmpsum] += 1\n",
    "            else:\n",
    "                d[tmpsum] = 1\n",
    "                \n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        result=0\n",
    "        sortlist=[0]\n",
    "        numcount=0\n",
    "        for i in range(len(nums)):\n",
    "            numcount+=nums[i]\n",
    "            index=bisect.bisect(sortlist,numcount-k)-1\n",
    "            while index>=0:\n",
    "                if sortlist[index]==numcount-k:\n",
    "                    result+=1\n",
    "                    index-=1\n",
    "                else:\n",
    "                    break\n",
    "            bisect.insort(sortlist,numcount)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # 思路：前缀和\n",
    "        memo = {0:1}\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # 更新前缀和\n",
    "            if i > 0:\n",
    "                nums[i] += nums[i-1]\n",
    "            # 计算差值\n",
    "            target = nums[i] - k\n",
    "            if target in memo:\n",
    "                ans += memo[target]\n",
    "            # nums[i]加入哈希表\n",
    "            if nums[i] not in memo:\n",
    "                memo[nums[i]] = 1\n",
    "            else:\n",
    "                memo[nums[i]] += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        dict = defaultdict(int)\n",
    "        dict[0] = 1\n",
    "        an=0\n",
    "        for i in range(len(nums)):\n",
    "            if i!=0:\n",
    "               nums[i] += nums[i-1]\n",
    "\n",
    "            if  nums[i] - k in dict:\n",
    "                an += dict[nums[i] - k]\n",
    "            dict[nums[i]] +=1\n",
    "            \n",
    "        return an\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums, k: int) -> int:\n",
    "        preSum = [0]\n",
    "        self.counter, self.lower, self.upper = 0, k, k\n",
    "        for num in nums:\n",
    "            preSum.append(preSum[-1]+num)\n",
    "        \n",
    "        self.mergeSort(preSum, 0, len(preSum)-1)\n",
    "        return self.counter\n",
    "\n",
    "    def mergeSort(self, nums, lo, hi):\n",
    "        if lo>=hi: return\n",
    "        mid = lo + ((hi-lo)>>1)\n",
    "        self.mergeSort(nums, lo, mid)\n",
    "        self.mergeSort(nums, mid+1, hi)\n",
    "\n",
    "        start, end = mid+1, mid+1 \n",
    "        for i in range(lo,mid+1):\n",
    "            while (start<=hi and (nums[start]-nums[i])<self.lower): start += 1\n",
    "            while (end<=hi and (nums[end]-nums[i])<=self.upper): end += 1\n",
    "            self.counter += (end-start)\n",
    "        \n",
    "        left, right = lo, mid+1\n",
    "        index, temp =lo, nums[lo:hi+1]\n",
    "        while(index<hi+1):\n",
    "            if left>mid:\n",
    "                nums[index] = temp[right-lo]\n",
    "                right += 1\n",
    "            elif right>hi:\n",
    "                nums[index] = temp[left-lo]\n",
    "                left += 1\n",
    "            elif temp[left-lo] <= temp[right-lo]:\n",
    "                nums[index] = temp[left-lo]\n",
    "                left += 1\n",
    "            else:\n",
    "                nums[index] = temp[right-lo]\n",
    "                right += 1\n",
    "            index += 1\n",
    "\n",
    "# A = Solution()\n",
    "# print(A.subarraySum([1,2,3],3))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        sum_map = {0:1}\n",
    "        cur_sum = 0\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            cur_sum += num\n",
    "            if cur_sum - k in sum_map:\n",
    "                cnt += sum_map[cur_sum - k] \n",
    "            if cur_sum in sum_map:\n",
    "                sum_map[cur_sum] += 1\n",
    "            else:\n",
    "                sum_map[cur_sum] = 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] = nums[i] + nums[i - 1]\n",
    "        res = {0: 1}\n",
    "        r = 0\n",
    "        for i in nums:\n",
    "            if i - k in res:\n",
    "                r += res[i - k]\n",
    "            if i in res:\n",
    "                res[i] += 1\n",
    "            else:\n",
    "                res[i] = 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # 数组中有正有负, 相同起点不同终点的多个子数组和可能都是k\n",
    "        # 前缀和+哈希表 哈希表中key为前缀和，value为前缀和的个数，前缀和表示当前元素之前的所有元素和\n",
    "        # 所以题目转化为当前节点和-k是否存在前缀和哈希表中，存在则返回个数\n",
    "        hash_tables = {0: 1}  # 初始化非常重要\n",
    "        # 记录当前前缀和与连续子数组的个数\n",
    "        nsum, count = 0, 0\n",
    "        # 遍历数组\n",
    "        for num in nums:\n",
    "            # 截止当前元素总和（下一个元素的前缀和）\n",
    "            nsum += num\n",
    "            # 判断nsum-k是否存在，存在则返回个数\n",
    "            count += hash_tables.get(nsum-k, 0)\n",
    "            # nsum加入哈希表\n",
    "            hash_tables[nsum] = hash_tables.get(nsum, 0) + 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        s,count = 0,0\n",
    "        record = {0:1}\n",
    "        for num in nums:\n",
    "            s += num\n",
    "            if s-k in record:\n",
    "                count += record[s-k]\n",
    "            if s not in record:\n",
    "                record[s] = 1\n",
    "            else:\n",
    "                record[s] += 1\n",
    "        return count\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int: \n",
    "        wdict = {0:1}\n",
    "        result = 0\n",
    "        for i in range(0, len(nums)):\n",
    "            if i > 0:\n",
    "                nums[i] += nums[i-1]\n",
    "            if nums[i] - k in wdict.keys():\n",
    "                result += wdict[nums[i]-k]\n",
    "            if nums[i] in wdict.keys():\n",
    "                wdict[nums[i]] += 1\n",
    "            else:\n",
    "                wdict[nums[i]] = 1\n",
    "            \n",
    "        return result\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        # 前缀和\n",
    "        temp_dict = {0: 1}\n",
    "        for i in range(0, len(nums)):\n",
    "            nums[i] = nums[i] + nums[i - 1] if i >= 1 else nums[i]\n",
    "            if nums[i] - k in temp_dict:\n",
    "                res += temp_dict[nums[i] - k]\n",
    "            if nums[i] in temp_dict:\n",
    "                temp_dict[nums[i]] += 1\n",
    "            else:\n",
    "                temp_dict[nums[i]] = 1\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        mp = {0:1}\n",
    "        pre = 0\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            pre += nums[i]\n",
    "            tmp = mp.get(pre - k, 0)\n",
    "            res += tmp\n",
    "            if pre in mp:\n",
    "                mp[pre] += 1\n",
    "            else:\n",
    "                mp[pre] = 1\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        dic = {0:1}\n",
    "        sums, res = 0, 0\n",
    "        for num in nums:\n",
    "            sums += num\n",
    "            res += dic.get(sums - k, 0)\n",
    "            dic[sums] = dic.get(sums, 0) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        forward_sum = []\n",
    "        curr_sum = 0\n",
    "        for num in nums:\n",
    "            curr_sum += num\n",
    "            forward_sum.append(curr_sum)\n",
    "        \n",
    "        subarr_cnt = {}\n",
    "        subarr_k_num = 0\n",
    "        for pre_sum in forward_sum:\n",
    "            if pre_sum == k:\n",
    "                subarr_k_num += 1\n",
    "\n",
    "            other_sum = pre_sum - k\n",
    "            if other_sum in subarr_cnt:\n",
    "                subarr_k_num += subarr_cnt[other_sum]\n",
    "            \n",
    "            if pre_sum in subarr_cnt:\n",
    "                subarr_cnt[pre_sum] += 1\n",
    "            else:\n",
    "                subarr_cnt[pre_sum] = 1\n",
    "        \n",
    "        return subarr_k_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        dic = {0:1}\n",
    "        sums,res = 0, 0\n",
    "        for num in nums:\n",
    "            sums+=num\n",
    "            res+=dic.get(sums-k,0)\n",
    "            print(sums-k)\n",
    "            dic[sums]=dic.get(sums,0)+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        l = len(nums)\n",
    "        \"\"\"METHOD 1 记忆化搜索 爆内存\"\"\"\n",
    "        # # F(i, k) = ONE(n[i]==k) + F(i+1, k-n[i]) F(i, k)是严格从i开始的\n",
    "        # F = collections.defaultdict(lambda: -1)\n",
    "        # def dfsSolve(i, m):\n",
    "        #     if i == len(nums):\n",
    "        #         return 0\n",
    "        #     if F[(i, m)] != -1:\n",
    "        #         return F[(i, m)] \n",
    "        #     var = 1 if nums[i] == m else 0\n",
    "        #     F[(i, m)] = var + dfsSolve(i+1, m-nums[i])\n",
    "        #     return F[(i, m)]\n",
    "        # for i in range(l):\n",
    "        #     dfsSolve(i, k)\n",
    "        # ans = 0\n",
    "        # for i in range(l):\n",
    "        #     a = F[(i, k)]\n",
    "        #     if a != -1:\n",
    "        #         ans += a\n",
    "        # return ans\n",
    "\n",
    "        \"\"\"METHOD 2 前缀和+HASH辅助遍历\"\"\"\n",
    "        P = [0]*l  # P[i] = SUM_{0, i}(nums[i])\n",
    "        table = {}\n",
    "        ans = 0\n",
    "\n",
    "        P[0] = nums[0]\n",
    "        if P[0] == k:\n",
    "            ans += 1\n",
    "        table[P[0]] = 1\n",
    "        table[0] = table.get(0, 0) + 1\n",
    "        \n",
    "        for i in range(1, l):\n",
    "            P[i] = P[i-1] + nums[i]\n",
    "            # if P[i] == k:\n",
    "            #     ans += 1\n",
    "            if P[i] - k in table:\n",
    "                ans += table.get(P[i]-k, 0)\n",
    "                print(i, ' ', ans)\n",
    "            # 必须放在后面，否则算上自己的话所得为空序列\n",
    "            table[P[i]] = table.get(P[i], 0) + 1\n",
    "        #     print(ans)\n",
    "        print(P, table)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # n = len(nums)\n",
    "        # sums = nums[:]\n",
    "        # ans = 0\n",
    "        # from collections import defaultdict\n",
    "        # num_dict = defaultdict(int)\n",
    "        # if sums[0] == k:\n",
    "        #     ans += 1\n",
    "        \n",
    "        # num_dict[sums[0]] += 1\n",
    "        # for i in range(1,n):\n",
    "        #     sums[i] += sums[i-1]   ### 0-i的和\n",
    "        #     num_dict[sums[i]] += 1\n",
    "        #     if sums[i] == k:\n",
    "        #         ans += 1\n",
    "\n",
    "\n",
    "        # for i in range(n-1):\n",
    "        #     num_dict[sums[i]] -= 1\n",
    "        #     ans += num_dict[sums[i]+k]\n",
    "        #     # for j in range(i+1, n):\n",
    "        #         # #### 其实是判断sums[j] == sums[i] + k的个数 （当然是j>i)\n",
    "        #         # if sums[j] - sums[i] == k:\n",
    "        #         #     ans += 1\n",
    "                \n",
    "        \n",
    "\n",
    "        # return ans\n",
    "\n",
    "        ans = 0\n",
    "        from collections import defaultdict\n",
    "        num_dict = defaultdict(int)\n",
    "        num_dict[0] = 1\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if i > 0:\n",
    "                nums[i] += nums[i-1]\n",
    "            \n",
    "            pre_num = nums[i] - k\n",
    "            ans += num_dict[pre_num]\n",
    "            num_dict[nums[i]] += 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        acc=list(accumulate(nums,initial=0))\n",
    "        ct=Counter(acc)\n",
    "        rs=0\n",
    "        used=defaultdict(int)\n",
    "        for i in range(len(acc)):\n",
    "            ct[acc[i]]-=1\n",
    "            rs+=ct[acc[i]+k]-used[acc[i]+k]\n",
    "        return rs    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "        Prefix Sum & Hash Table\n",
    "        - 將問題轉換成 prefix_sum[j] - prefix_sum[i] = k ，且 i < j 的個數\n",
    "        - 注意：不能用Sliding Window，因為nums中有負數\n",
    "    \"\"\"\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        cnt = defaultdict(int) # tbl[s] = prefix sum 為 s 的個數\n",
    "        cnt[0] = 1\n",
    "        pre = 0 # prefix_sum\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            pre += num # pre = prefix_sum[j]\n",
    "            ans += cnt[pre-k] # pre-k = prefix_sum[i] 的個數\n",
    "            cnt[pre] += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
